package comUtils;

public class SBSTree<T extends Comparable<T>>{
	SBSNode<T> root;
	
	public class SBSNode<S extends T>{
		T key;
		SBSNode<T> left;
		SBSNode<T> right;
		public SBSNode(T key, SBSTree<T>.SBSNode<T> left,
				SBSTree<T>.SBSNode<T> right) {
			super();
			this.key = key;
			this.left = left;
			this.right = right;
		}
	}
	
	/**@description
	 * 判断SBS类型的节点是否为空
	 */
	public boolean isNull(SBSNode<T> sBSNode){
		return null==sBSNode? true:false;
	}
	
	/**@description
	 * 判断SBS类型的节点是都不为空
	 */
	public boolean isNotNull(SBSNode<T> sBSNode){
		return !isNull(sBSNode);
	}
	
	/**@description
	 * 显式的进行初始化
	 */
	public void init(){
		root = null;
	}
	
	/**@description
	 * 判断树是否为空
	 */
	public boolean isEmpty(){
		return isNull(root);
	}
	
	/**@description
	 * 左左旋转:插入或删除一个节点后，根节点的左子树的左子树还有非空子节点
	 */
	private SBSNode<T> LLRotate(SBSNode<T> bBSNode){
		SBSNode<T> LNode = bBSNode.left;
		bBSNode.left = LNode.right;
		LNode.right = bBSNode;
		return LNode;
	}
	
	/**@description
	 * 右右旋转:插入或删除一个节点后，根节点的右子树的右子树还有非空子节点
	 */
	private SBSNode<T> RRRotate(SBSNode<T> bBSNode){
		SBSNode<T> LNode = bBSNode.right;
		bBSNode.right = LNode.left;
		LNode.left = bBSNode;
		return LNode;
	}
	
	/**@description 
     * 返回key所在的节点(中序查找所有节点) 
     */  
    public SBSNode<T> findAllNode(T key){
    	if(isNull(root)){
    		return null;
    	}else{
    		SBSNode<T> node = middleFindByKey(root,key);
    		if(isNotNull(node)){
    	       	root = rotateTree(root, node.key);
    	     }else{
    	     }
    	    return node;
    	}
    }  
    
    public SBSNode<T> middleFindByKey(SBSNode<T> treeNode,T key){  
    	SBSNode<T> sBSNode = null;  
        /*优先查找左自树*/  
        if(isNotNull(treeNode.left)){  
        	sBSNode = middleFindByKey(treeNode.left,key);  
            if(isNotNull(sBSNode)){  
                return sBSNode;  
            }  
        }else{  
        }  
        /*查找中间节点*/  
        if(0 == treeNode.key.compareTo(key)){  
            return sBSNode = treeNode;  
        }else{  
        }  
        /*查找右子树*/  
        if(isNotNull(treeNode.right)){  
        	sBSNode = middleFindByKey(treeNode.right,key);  
            if(isNotNull(sBSNode)){  
                return sBSNode;  
            }   
        }else{  
        }  
        return sBSNode;  
    }
	
	/**@description 
	 * 添加节点
	 */
	public boolean addSBSNode(T key){
		/*判断添加节点是否成功*/
		boolean result = true;
		SBSNode<T> sBSNode = new SBSNode<T>(key, null, null);
		if(isNull(sBSNode)){
			System.out.println("节点生成失败");
			return !result;
		}
		if(isEmpty()){
			root = sBSNode;
		}else{
			insert(root,sBSNode);
			/*插入节点之后则key所在节点一定存在，然后旋转节点，且赋值给根节点*/
			root = rotateTree(root,key);
		}
		return result;
	}
	
	/**@description 
	 * 添加节点
	 */
	private boolean insert(SBSNode<T> tree,SBSNode<T> sBSNode){
		/*判断添加节点是否成功*/
		boolean result = true;
		if(sBSNode.key.compareTo(tree.key) < 0){
			if(isNotNull(tree.left)){
				result = insert(tree.left,sBSNode);
			}else{
				tree.left = sBSNode;
			}
		}else if(sBSNode.key.compareTo(tree.key) > 0){
			if(isNotNull(tree.right)){
				result = insert(tree.right,sBSNode);
			}else{
				tree.right = sBSNode;
			}
		}else{/*值相等什么也不做*/
			result = false;
		}
		return result;
	}
	/**@description 
	 * 旋转节点
	 */
	private SBSNode<T> rotateTree(SBSNode<T> tree,T key){
		if(key.compareTo(tree.key) < 0){
			if(isNotNull(tree.left)){ /*左边树不为空*/
				if(key.compareTo(tree.left.key) < 0){
					tree = LLRotate(tree);
					tree = rotateTree(tree, key);
				}else if(key.compareTo(tree.left.key) > 0){
					tree.left = rotateTree(tree.left, key);
					tree = LLRotate(tree);
				}else{/*直接左旋转*/
					tree = LLRotate(tree);
				}
			}else{/*左边树为空,说明没有该节点，这种情形不存在*/
			}
		}else if(key.compareTo(tree.key) > 0){
			if(isNotNull(tree.right)){
				if(key.compareTo(tree.right.key) > 0){
					tree = RRRotate(tree);
					tree = rotateTree(tree, key);
				}else if(key.compareTo(tree.right.key) < 0){
					tree.right = rotateTree(tree.right, key);
					tree = RRRotate(tree);
				}else{
					/*直接右旋转*/
					tree = RRRotate(tree);
				}
			}else{/*右边树为空,说明没有该节点，这种情形不存在*/
			}
		}else{/*这种情形只能是根节点*/
			return tree;
		}
		return tree;
	}
	
	 /**@description  
     * 前序遍历 
     */  
    public void beforeFind(SBSNode<T> treeNode){  
        if(isNotNull(treeNode)){  
        	System.out.print(treeNode.key+" ");  
            beforeFind(treeNode.left);  
            beforeFind(treeNode.right);  
        }else{  
        }  
    }  
    public void beforeFind(){  
        beforeFind(root);  
    }  
      
    /**@description  
     * 中序遍历 
     */  
    public void middleFind(SBSNode<T> treeNode){  
        if(isNotNull(treeNode)){  
            middleFind(treeNode.left);  
            System.out.print(treeNode.key+" ");  
            middleFind(treeNode.right);  
        }else{  
        }  
    }  
    public void middleFind(){  
        middleFind(root);  
    }  
      
    /**@description  
     * 后序遍历 
     */  
    public void afterFind(SBSNode<T> treeNode){  
        if(isNotNull(treeNode)){  
            afterFind(treeNode.left);  
            afterFind(treeNode.right);  
            System.out.print(treeNode.key+" ");  
        }else{  
        }  
    }  
    public void afterFind(){  
        afterFind(root);  
    } 

    public static void main(String[] args) {
		SBSTree<Integer> bBSTree = new SBSTree<Integer>();
		/*新增数据*/
		bBSTree.addSBSNode(new Integer(40));
		bBSTree.addSBSNode(new Integer(20));
		bBSTree.addSBSNode(new Integer(60));
		bBSTree.addSBSNode(new Integer(50));
		bBSTree.addSBSNode(new Integer(70));
		bBSTree.addSBSNode(new Integer(45));
		bBSTree.addSBSNode(new Integer(7));
		bBSTree.addSBSNode(new Integer(8));
		bBSTree.findAllNode(45);
		bBSTree.findAllNode(70);
//		bBSTree.delBSNode(50);
//		bBSTree.delBSNode(70);
//		bBSTree.delBSNode(45);
		
		bBSTree.middleFind();
		System.out.println();
		bBSTree.beforeFind();
		System.out.println();
		bBSTree.afterFind();
	}
}
